package com.cat.chapter045;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author cat
 * @description https://leetcode.cn/problems/word-search-ii/description/
 * @create 2025/7/15 09:14
 * @since JDK17
 */

public class Solution04 {
    static int MAXN = 100001;
    static int[][]tree = new int[MAXN][26];
    int cnt = 1;
    static int[] pass = new int[MAXN];
    static String[] end = new String[MAXN];
    static List<String> ans = new ArrayList<>();
    public int dfs(int i, int j, int cur, char[][] board) {
        if (i < 0 || j < 0 || i == board.length || j == board[0].length) {
            return 0;
        }
        char temp = board[i][j];
        int path = temp - 'a', next = tree[cur][path], fix = 0;
        if (pass[next] == 0) { // 没有路或者无利可图了
            return 0;
        }

        if (end[next] != null) {    // 找到了一个单词
            fix++;
            ans.add(end[next]);
            end[next] = null;
        }

        fix += dfs(i + 1, j, next, board);
        fix += dfs(i - 1, j, next, board);
        fix += dfs(i, j + 1, next, board);
        fix += dfs(i, j - 1, next, board);
        pass[next] -= fix;
        board[i][j] = temp;
        return fix;
    }

    public List<String> findWords(char[][] board, String[] words) {

        int n = board.length, m = board[0].length;
        for (String word : words) { // 将字符串插入到前缀树中
            insert(word);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dfs(i, j, 1, board);
            }
        }
        return ans;
    }

    void insert(String word) {
        int cur = 1;
        pass[cur]++;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) { //
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
        end[cur] = word;
    }

    void clear() {
        for (int i = 0; i < cnt; i++) {
            Arrays.fill(tree[i], 0);
            end[i] = null;
            pass[i] = 0;
        }
        cnt = 1;
        ans = new ArrayList<>();
    }
}
